#include <iostream>
using namespace std;

// 用第一个元素将待排序序列划分为左右两个部分
template <typename T> //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于(>)运算符
int Paritition(T A[], int low, int high)
{
  T pivot = A[low]; // 第一个元素作为基准（枢轴）
  while (low < high)
  { // 用low、high搜索枢轴的最终位置
    while (low < high && A[high] >= pivot)
    {
      --high;
    }
    A[low] = A[high]; // 比枢轴小的元素移动到左边
    while (low < high && A[low] <= pivot)
    {
      ++low;
    }
    A[high] = A[low]; // 比枢轴大的元素移动到右边边
  }
  A[low] = pivot; // 枢轴元素存放到最终位置
  return low;     // 返回存放枢轴的最终位置
}

template <typename T>                    //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于(>)运算符
void QuickSort(T A[], int low, int high) //快排母函数
{
  if (low < high)
  {                                           // 递归跳出的条件
    int pivotpos = Paritition1(A, low, high); // 划分
    QuickSort(A, low, pivotpos - 1);          // 划分左子表
    QuickSort(A, pivotpos + 1, high);         // 划分右子表
  }
}

int main()
{
  int arr[] = {61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62};
  int len = (int)sizeof(arr) / sizeof(*arr);
  QuickSort(arr, 0, len - 1);
  for (int i = 0; i < len; i++)
    cout << arr[i] << ' ';
  cout << endl;

  float arrf[] = {17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.8, 5.4};
  len = (int)sizeof(arrf) / sizeof(*arrf);
  QuickSort(arrf, 0, len - 1);
  for (int i = 0; i < len; i++)
    cout << arrf[i] << ' ' << endl;
  return 0;
}
